package  main.java.leetcode.editor.cn;
//2022-04-18 17:17:31
//给定一个单链表 L 的头节点 head ，单链表 L 表示为： 
//
// L0 → L1 → … → Ln-1 → Ln 
//请将其重新排列后变为： 
//
// L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 
//
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: head = [1,2,3,4]
//输出: [1,4,2,3] 
//
// 示例 2: 
//
// 
//
// 
//输入: head = [1,2,3,4,5]
//输出: [1,5,2,4,3] 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 5 * 104] 
// 1 <= node.val <= 1000 
// 
//
// 
//
// 注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/ 
// Related Topics 栈 递归 链表 双指针 
// 👍 47 👎 0

import java.util.Stack;

class LGjMqU {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new LGjMqU().new Solution();
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for(int i = 2;i<=5;i++){
            ListNode node = new ListNode(i);
            cur.next = node;
            cur = cur.next;
        }
        solution.reorderList(head);
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null){
            return;
        }
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null){
            stack.add(cur.val);
            cur = cur.next;
        }
        ListNode newHead = head;
        int length = stack.size();
        for(int i = 0;i<length/2;i++){
            ListNode curr = newHead.next;
            ListNode stackNode = new ListNode(stack.pop());
            newHead.next = stackNode;

            if(i == length/2-1 && length%2 == 0){
                return;
            }

            if(i == length/2-1 && length%2 == 1){
                ListNode stackNode1 = new ListNode(stack.pop());
                newHead.next.next = stackNode1;
                return;
            }
            newHead.next.next = curr;
            newHead = curr;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
